package com.jacklei;

import com.jacklei.util.ArrUtil;

import java.util.Arrays;

//快速排序 3.0
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = ArrUtil.getRandomArr();
        int[] arr1 = ArrUtil.copyArr(arr);
        Arrays.sort(arr);
        sort(arr1);
        ArrUtil.checkArr(arr, arr1);

        ArrUtil.seeArr(arr, arr1);

    }
    public static void sort(int[] arr){
        sort(arr, 0, arr.length-1);
    }
    public static void sort(int[] arr,int l, int r){
        if(l >= r ) return;
        int index = l+((int) (Math.random() * 100)) % (r-l);
        ArrUtil.swap(arr, index, r);
        int[] partition = partition(arr, l, r);
        //if(partition[1] == partition[0]) return;
        sort(arr, l, partition[0] - 1);
        sort(arr, partition[1] + 1, r);
    }
    private static int[] partition(int[] arr, int l, int r) {
        int LStart = l;
        int RStart = r;
        int index = l;
        final int  medianValue = arr[r];
        while(index <= RStart){
            if(arr[index] > medianValue){
                //比目标值大
                ArrUtil.swap(arr, index, RStart--);
            }
            if(arr[index] < medianValue){
                //比目标值小
                ArrUtil.swap(arr, index++, LStart++);
            }
            if(arr[index] == medianValue){
                //等于
                index ++;
            }
        }
        return new int[] {LStart,RStart};
    }

}
